/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/minimum-path-sum
   @Language: C++
   @Datetime: 16-02-09 05:12
   */

class Solution {
public:
	/**
	 * @param grid: a list of lists of integers
	 * @return: An integer, minimizes the sum of all numbers along its path
	 */
	int minPathSum(vector<vector<int>> &grid) {
		// write your code here
		if(grid.size()<1) return 0;
		int n=grid.size(), m=grid[0].size();
		for(int i=0; i<n; ++i){
			for(int j=0; j<m; ++j){
				if(i==0 && j==0) continue;
				if(i>0 && j>0) grid[i][j]+=min(grid[i][j-1],grid[i-1][j]);
				else if(i>0) grid[i][j]+=grid[i-1][j];
				else if(j>0) grid[i][j]+=grid[i][j-1];
			}
		}
		return grid[n-1][m-1];
	}
};
